package com.chj.lintcode.backpack;

public class Code04_backpackIV {
	/**
	 * @param nums: an integer array and all positive numbers, no duplicates
	 * @param target: An integer
	 * @return: An integer
	 */
	public static int backPackIV(int[] nums, int target) {
		// write your code here
		int n = nums.length;
		int[][] dp = new int[n + 1][target + 1];
		dp[0][0] = 1;

		for (int i = 1; i <= target; i++) {
			dp[0][i] = 0;
		}

		for (int i = 1; i <= n; i++) {
			for (int j = 0; j <= target; j++) {
				dp[i][j] = dp[i - 1][j];
				if (j >= nums[i - 1]) {
					dp[i][j] = dp[i - 1][j] + dp[i][j - nums[i - 1]];
				}
//				else {
//					dp[i][j] = dp[i - 1][j];
//				}
			}
		}

		return dp[n][target];
	}

//	https://www.lintcode.com/problem/backpack-iv/note/228328
	public static void main(String[] args) {
		{
			int[] nums = { 2, 3, 6, 7 };
			int target = 7;
			System.out.println(backPackIV(nums, target));
		}

		{
			int[] nums = { 2, 3, 4, 5 };
			int target = 7;
			System.out.println(backPackIV(nums, target));
		}
	}
}
